// 与104类似，只不过数据结构不同，在遍历时相应修改代码

// Definition for a Node.
class Node {
 public:
  int val;
  vector<Node*> children;

  Node() {}

  Node(int _val) { val = _val; }

  Node(int _val, vector<Node*> _children) {
    val = _val;
    children = _children;
  }
};
* /

    class Solution {
 public:
  // 后序遍历
  /*
  int maxDepth(Node* root) {
      if(!root) return 0;
      int c = 0;
      for(auto& t : root->children) {
          c = max(c,maxDepth(t));
      }
      return 1+c;
  }
  */
  // 层次遍历
  /*
  int maxDepth(Node* root) {
      if(!root) return 0;
      queue<Node*> que;
      int size;
      int depth=0;
      Node* temp;
      que.push(root);
      while(!que.empty()) {
          size = que.size();
          for(int i = 0;i < size; i++) {
              temp = que.front();
              que.pop();
              for(auto& t : temp->children) {
                  que.push(t);
              }
          }
          depth++;
      }
      return depth;
  }
  */
  // 前序遍历,求深度
  int result = 0;
  int maxDepth(Node* root) {
    if (!root) return 0;
    GetDepth(root, 1);
    return result;
  }
  void GetDepth(Node* root, int depth) {
    result = max(result, depth);
    if (!root) return;
    for (auto& t : root->children) {
      GetDepth(t, depth + 1);
    }
  }
};
